﻿using System;
using System.Diagnostics;
using System.Collections;

namespace MikeKappel.Com.CS
{
    public static partial class SortingAlgorithms
    {
        public delegate Boolean RadixDelegate(Int32 currentIndex, Int32 currentValue);

        /// <summary>
        /// 
        /// </summary>
        /// <param name="onSort">On value change method to fire</param>
        /// <param name="ittems">Array of Integers to sort</param>
        public static void RadixSort(Int32[] items, RadixDelegate onSort)
        {
            Int32[] t = new Int32[items.Length];
            Int32 r = 4; 
            Int32 b = 32; 
            Int32[] count = new Int32[1 << r];
            Int32[] pref = new Int32[1 << r];

            Int32 groups = (Int32)Math.Ceiling((Double)b / (Double)r);

            Int32 mask = (1 << r) - 1;

            for (Int32 c = 0, shift = 0; c < groups; c++, shift += r)
            {
                for (Int32 j = 0; j < count.Length; j++)
                {
                    if (onSort != null && !onSort(j, j))
                        goto escape;

                    count[j] = 0;
                }

                for (Int32 i = 0; i < items.Length; i++)
                {
                    if (onSort != null && !onSort(i, items[i]))
                        goto escape;

                    count[(items[i] >> shift) & mask]++;
                }

                pref[0] = 0;
                for (Int32 i = 1; i < count.Length; i++)
                {
                    if (onSort != null && !onSort(i, pref[i]))
                        goto escape;

                    pref[i] = pref[i - 1] + count[i - 1];
                }

                for (Int32 i = 0; i < items.Length; i++)
                {
                    if (onSort != null && !onSort(i, items[i]))
                        goto escape;

                    t[pref[(items[i] >> shift) & mask]++] = items[i];
                }

                t.CopyTo(items, 0);
            }

        escape:
            return;
        }
        public static void RadixSort(Int32[] items)
        {
            RadixSort(items, null);
        }
    }
}
